package com.yitiao.data_algorithms.leetcode.editor.cn;

class TwoVG8Kg{
    // 2023-04-03 18:02:04
    public static void main(String[] args) {
        Solution solution = new TwoVG8Kg().new Solution();
    }
    
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int ans = Integer.MAX_VALUE;
        if (nums.length == 0) return 0;
        // 构建 前缀和 单调递增
        int[] sum = new int[nums.length + 1];
        for (int i = 1; i < sum.length; i++) {
            sum[i] = nums[i - 1] + sum[i - 1];
        }

        for (int i = 0; i < sum.length; i++) {
            int s = sum[i];
            // 在前缀和数组 二分查找
            int left = 0, right = i;
            while (left < right) {
                int mid = (left + right + 1) / 2;
                if (sum[mid] <= s - target) {
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            if (sum[right] <= s - target) {
                ans = Math.min(ans, i - right);
            }
        }
        return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}